/**
 * MaxIntHeap.java
 *
 *
 * Created: Mon Jul 8 13:07:49 2002
 *
 * @author Scott Sanner - intern
 * @version 1.0
 */
package mahmoud.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

/**
 * A heap implementation for priority queue type operations.
 * Assumes (-1) is an invalid value.
 */
public class MaxHeap<T> {

	// Note, for arithmetic efficiency and clarity, a[1]
	// is the first.  Actual array size is always at least
	// 1 + sz.
	private Comparable<T>[] a;                       // array
	private int   sz = 0;                 // num elements

	private int DEF_SZ = 32; // default heap size

	/**
	 * Build a priority queue from scratch
	 */
	public MaxHeap() {
		a  = new Comparable[DEF_SZ];
		sz = 0;
	}
	public MaxHeap(int size)
	{
		DEF_SZ= size;
		sz = 0;
		a = new Comparable[size+1];
	}

	/**
	 * Build a priority queue from an integer array
	 */ 
	public MaxHeap(int[] val, int size)
	{
		a = new Comparable[size + 1];

		// a[1] is the first element, a[0] is unused
		System.arraycopy(val, 0, a, 1, size);
		sz = size;
		buildHeap();
	}

	/**
	 * Turn the array into a heap
	 */
	public int size()
	{
		return sz;
	}
	public void buildHeap() {
		for (int i = sz >> 1; i >= 1; i--) {
			heapify(i);
		}
	}

	/**
	 * Heapify the subtree rooted at node i, and recurse the swapped
	 * subtree
	 */
	public void heapify(int i) {

		int l, r, largest;
		boolean cont = true;

		while (cont) {

			l = 2 * i; // The left subnode
			r = l + 1; // The right subnode

			if(l <= sz && a[l].compareTo((T)a[i])>0)  
				largest = l;
			 else 
				largest = i;
				    

			if (r <= sz && a[r].compareTo((T)a[largest])>0) 
				largest = r;

			if (largest != i) 
			{
				Comparable<T> temp = a[i];
				a[i] = a[largest];
				a[largest] = temp;
				i = largest; // heapify(largest)
			} 
			else
				cont = false; // No need to recurse
		}
	}

	/**
	 * Insert an element into the queue
	 */
	public void add(Comparable<T> key) 
	{
		// Expand the array?
		if(!isFull())
			addkey(key);
		else if(this.max().compareTo((T) key)>0)
		{
			this.removeMax();
			addkey(key);
		}
	}

	private void addkey(Comparable<T> key)
	{
		int cld = ++sz;
		int parent;
		while (cld > 1 && a[parent = (cld >> 1)].compareTo((T) key)<0) 
		{
			a[cld] = a[parent];
			 cld= parent;
		}
		a[cld] = key;
	}

	/**
	 * Remove the max element from the queue
	 */
	public Comparable<T> removeMax() 
	{
		if (sz == 0) 
			return (null);
		Comparable<T> max = a[1];
		a[1] = a[sz];
		sz--;
		heapify(1);
		return max;
	}

	/**
	 * Check the max element in the queue but do not remove
	 */
	public Comparable<T> max() 
	{
		if (sz > 0) 
			return a[1];
		else 
			return (null);
	}

	/**
	 * Is heap empty?
	 */
	public boolean isEmpty() 
	{
		return (sz == 0);
	}
	public boolean isFull()
	{
		return (sz >= DEF_SZ);
	}
	/**
	 * Print the current heap
	 */
	public String printHeap() {
		StringBuffer sb1 = new StringBuffer();
		StringBuffer sb2 = new StringBuffer();
		for (int i = 1; i <= sz; i++) {
			sb1.append(i + " ");
			sb2.append(a[i] + " ");
		}
		return sb2.toString() + "\n" + sb1.toString();
	}

	/**
	 * Testing method
	 */

	public static void main(String args[]) 
	{
		int top =10;
		int total = 50;
		int maxRand = 100;
		boolean testFailed = false;
		ArrayList<Integer> fromArrayList = new ArrayList<Integer>();
		ArrayList<Integer> fromHeap = new ArrayList<Integer>();
		Random gen = new Random();

		for(int i = 0 ; i<total ; i++)
		{
			fromArrayList.add(gen.nextInt(maxRand));
		}

		MaxHeap<Integer> h = new MaxHeap<Integer>(top);
		for (Integer x : fromArrayList)
		{
			System.out.println("Trying to insert "+ x);
			h.add(x);
			System.out.println("Heap contents: "+ h.printHeap()+"\nHeap Max\t"+h.max()+"\n");
		}
		//		System.exit(0);
		//save the heap-selected top results to an arraylist 
		while (!h.isEmpty())
		{
			fromHeap.add((Integer) h.removeMax());
		}

		Collections.sort(fromArrayList);
		ArrayList<Integer>  al = new ArrayList<Integer>( fromArrayList.subList(0, top));
				Collections.sort(al,Collections.reverseOrder());
		//		Collections.sort(al);
		for (int j = 0; j< top ; j++)
		{
			//			System.out.println("AL : "+al.get(j)+ "\t From Heap: "+fromHeap.get(j));
			if(!fromHeap.get(j).equals(al.get(j))  )
			{
				System.out.println("AT Index : "+j+" AL : "+al.get(j)+ "\t From Heap: "+fromHeap.get(j));
				testFailed= true;
			}
		}
		if(testFailed)
			System.out.println("The HEap didnt work as expected");
		else
			System.out.println("Test Successfull..!");

	}
}
